//You are given a string s. You can convert s to a palindrome by adding characte
//rs in front of it. 
//
// Return the shortest palindrome you can find by performing this transformation
//. 
//
// 
// Example 1: 
// Input: s = "aacecaaa"
//Output: "aaacecaaa"
// Example 2: 
// Input: s = "abcd"
//Output: "dcbabcd"
// 
// 
// Constraints: 
//
// 
// 0 <= s.length <= 5 * 104 
// s consists of lowercase English letters only. 
// 
// Related Topics 字符串 字符串匹配 哈希函数 滚动哈希 
// 👍 378 👎 0


package leetcode.editor.cn;

//Java：Shortest Palindrome
class P214ShortestPalindrome {
    public static void main(String[] args) {
        Solution solution = new P214ShortestPalindrome().new Solution();
        // TO TEST
        System.out.println(solution.shortestPalindrome("aacecaaa"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String shortestPalindrome(String s) {
            String max = s;
            int len = s.length();
            for (int i = 0; i < len - 1; i++) {
                for (int j = i + 1; j < len; j++) {
                    if (isPalindrome(s, i, j)) {
                        max = max.length() > j - i ? s.substring(i, j + 1) : max;
                    }

                }
            }
            return max;
        }

        public boolean isPalindrome(String s, int i, int j) {
            while (i < j) {
                if (s.charAt(i++) == s.charAt(j--)) {
                    continue;
                }
                return false;
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}